Consider the number of the form a ^ (a ^ (a ^ ...) where a is a positive integer
that can appear in the notation twice or more, ^ is power operation. Let us
call such numbers numbairs (which stands for number + stairs). For instance 27
= 3 ^ 3 and 16 = 2 ^ (2 ^ 2) are numbairs. Number 1 is numbair too since 1 = 1
^ 1. Find out how many numbairs are there between 1 and n inclusive.
Input. One integer n (1
≤ n ≤ 109).
Output. Print the
number of numbairs not exceeding n.
|
Sample input |
Sample output |
|
5 |
2 |
mathematics
Algorithm
analysis
The
numbairs are growing quickly, let’s find
all of them which are not greater than 109.
They are: 1^1 = 1, 2^2 = 4, 2^(2^2) = 16, 2^(2^(2^2)) = 2^16 = 65536, 3^3,
4^4, …, 9^9 = 387420489.
Algorithm
realization
Read the value of n. Count the number of numbairs in the variable ans.
scanf("%d",&n);
int ans = 0;
if (n >= 1) ans++; // 1^1
if (n >= 4) ans++; //
2^2
if (n >= 16) ans++; //
2^(2^2)
if (n >= 65536) ans++; //
2^(2^(2^2))
if (n >= 3*3*3) ans++; // 3^3
if (n >= 4*4*4*4) ans++; // 4^4
if (n >= 5*5*5*5*5) ans++; // 5^5
if (n >= 6*6*6*6*6*6) ans++; // 6^6
if (n >= 7*7*7*7*7*7*7) ans++; // 7^7
if (n >= 8*8*8*8*8*8*8*8) ans++; // 8^8
if (n >= 9*9*9*9*9*9*9*9*9) ans++; // 9^9
Print the answer.
printf("%d\n",ans);